package Hash.Medium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class LC0049 {
    /**
     * 这种解法将所有字母排完序后的字符串（“正则化字符串”）作为HashMap的key。
     * 一种更高效的解法是统计每个字母的出现词数，并把(字母+出现次数)这样的组合连成字符串，作为HashMap的key。详见
     * https://leetcode.cn/problems/group-anagrams/solutions/520469/zi-mu-yi-wei-ci-fen-zu-by-leetcode-solut-gyoc/?envType=study-plan-v2&envId=top-100-liked
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, ArrayList<String>> canonicalStrMap = new HashMap<>(); // 正则化字符串（所有字母排列过的字符串）到原始字符串的映射
        for (int i = 0; i < strs.length; i++) {
            // 获取正则化字符串
            String oriStr = strs[i];
            char[] charArray = oriStr.toCharArray();
            Arrays.sort(charArray);
            String canonicalStr = new String(charArray);

            if (!canonicalStrMap.containsKey(canonicalStr)) {
                canonicalStrMap.put(canonicalStr, new ArrayList<>());
            }
            canonicalStrMap.get(canonicalStr).add(oriStr);
        }

        ArrayList<List<String>> ret = new ArrayList<>();
        for (String key : canonicalStrMap.keySet()) {
            ret.add(canonicalStrMap.get(key));
        }

        return ret;
    }
}
